#include <iostream>
using namespace std;

#include "ProgCommon.h"


int candicate( int a[], int m, int n )
{
    int j = m;
    int c = a[m];
    int count = 1;

    while ( j < n && count > 0 ) {
        j++;
        if ( a[j] == c ) {
            count += 1;
        } else {
            count -= 1;
        }
    }

    if ( j == n ) {
        return c;
    } else {
        return candicate( a, j+1, n );
    }
}

int majority( int a[], int n, int& cnt )
{
    int c = candicate( a, 1, n );
    int count = 0;

    for ( int j = 1; j <= n; j++ ) {
        if ( a[j] == c )
            count += 1;
    }

    cnt = count;

    if ( count > ( n/2 ) )
        return c;

    return -1;
}

int main()
{
    PROG_BANNER;
    RAND_SEED;

    int n = RandomInt( 7, 12 );
    int *pLst = new int[n+1];
    int ret, cnt, i;

    ConSetColor( FG_CYAN );
    printf( "Prog 1: Majority num in array\n" );
    ConSetColor( COLOR_DEFAULT );

    printf( "Random array is: [ " );
    for ( i = 1; i <= n; i++ ) {
        pLst[i] = RandomInt( 1, n/4 + 2 );
        cout << pLst[i] << " ";
    }
    printf( "]\n");

    ret = majority( pLst, n, cnt );

    if ( -1 != ret ) {
        printf( " * Majority num is " );
        ConSetColor( FG_RED );
        printf( "%d\n", ret );
        ConSetColor( COLOR_DEFAULT );
        printf( "For cnt is %d > %d/2=%d\n", cnt, n, n/2 );
    }
    else {
        ConSetColor( FG_RED );
        printf( " * No Majority num\n" );
        ConSetColor( COLOR_DEFAULT );
    }

    PROG_BANNER;
    PROG_PAUSE;
    return 0;
}

